#include <stdio.h>
#include <stdlib.h>

typedef struct _Node{
    int data;
    struct _Node *next;
}node_t;

// 创建循环链表 将 1-n 插入链表中 并返回 1那个节点的地址
node_t *create_list_and_insert_data(int n){
    node_t *phead = (node_t *)malloc(sizeof(node_t));
    if(NULL == phead){
        return NULL;
    }
    phead->data = 1;
    phead->next = NULL;
    // 循环将 [2,n] 插入到链表中
    node_t *pnew = NULL;
    node_t *ptail = phead;
    for(int i = 2; i <= n; i++){
        pnew = (node_t *)malloc(sizeof(node_t));
        if(NULL == pnew){
            return NULL;
        }
        pnew->data = i;
        ptail->next = pnew;
        ptail = pnew;
    }
    // 尾节点指针域指向开头  构成循环链表
    ptail->next = phead;
    return phead;
}

int main(int argc, const char *argv[]){
    // 判断执行程序时参数的格式是否正确
    if(3 != argc){
        printf("Usage : %s  总人数  数到几\n", argv[0]);
        return -1;
    }
    // 获取命令行传入的总人数
    int total_person_num = atoi(argv[1]);
    // 获取命令行传入的数到几
    int count = atoi(argv[2]);
    // 判断入参是否合理
    if(total_person_num <= 1 || count <= 1){
        printf("输入的参数不合理  请重新执行\n");
        return -1;
    }
    // 创建循环链表  将 [1, total_person_num] 插入到链表中
    node_t *phead = create_list_and_insert_data(total_person_num);

    // 先打印一下链表中所有元素 确认插入成功
    // node_t *ptemp = phead;
    // do{
    //     printf("%d ", ptemp->data);
    //     ptemp = ptemp->next;
    // }while(ptemp != phead);
    // printf("\n");

    // 开始执行淘汰的过程
    node_t *prev = phead; // 用来保存phead前一节点 删除phead时使用
    int num = 0; // 用来计数已经数到几了
    int n = 0; // 用来计数第几次淘汰
    while(phead->next != phead){
        num++;
        if(num == count){ // 该淘汰了
            // 先输出
            printf("第 %d 次 淘汰的是 %d 号\n", ++n, phead->data);
            // 删除要淘汰的节点(phead指向的节点)
            prev->next = phead->next;
            free(phead);
            phead = prev->next;
            // 计数值清0
            num = 0;
        }else{ // 还没到该淘汰的时候
            prev = phead;
            phead = phead->next;
        }
    }
    printf("最后剩下的是 %d 号\n", phead->data);
    free(phead);
    phead = NULL;
    return 0;
}